package wtx.geek;

import java.util.*;
import java.util.Random;


/**
 * Imagine an alphabet of words. Example:
 a ==> 1
 b ==> 2
 c ==> 3
 .
 z ==> 26
 ab ==> 27
 ac ==> 28
 .
 az ==> 51
 bc ==> 52
 and so on.

 Such that the sequence of characters need to be in ascending order only (ab is valid but ba is not). Given any word print its index if valid and 0 if not.

 Input Output
 ab 27
 ba 0
 aez 441

 cde        ----> 928
 --------------------------------
 cdb        ----> 0
 --------------------------------
 cdf        ----> 929
 --------------------------------
 moqx       ----> 16983
 --------------------------------
 xyz        ----> 2951
 --------------------------------
 hjmoqsu    ----> 930152
 Note: Brute-force is not allowed.

 **/

public class Solution {
  /**
   * incr数组中保存长度为i+1且以字符j+'a'开头的这个区间内所有组合的个数
   * accu则表示长度为i+1且以字符j+'a'开头的这个区间能表示的最大数。相当于把
   * incr中[i,j]这个位置之前的元素进行累加
   */
  static long incr[][] = new long[26][26];
  static long accu[][] = new long[26][26];
  static {
    for (int i = 0; i < 26; ++i) {
      incr[0][i] = 1;
    }
    for (int i = 1; i < 26; i++) {
      for (int j = 0; j < 26; j++) {
        for (int k = j+1; k < 26; ++k) {
          incr[i][j] = incr[i][j] + incr[i-1][k];
        }
      }
    }
    accu[0][0] = 1;
    for (int i = 0; i < 26; ++i) {
      for (int j = 0; j < 26; ++j) {
        if (j != 0) {
          accu[i][j] = accu[i][j - 1] + incr[i][j];
        } else {
          if (i != 0) {
            accu[i][j] = accu[i-1][25] + incr[i][j];
          }
        }
      }
    }
  }
  public long getNumberFromChar(char[] array) {
    final int len = array.length;
    long result = 0;
    char lastChar = 'a';
    for (int i = 0; i < len; ++i) {
      if (i == 0) {
        lastChar = array[i];
      } else {
        if (array[i] <= lastChar) {
          return 0L;
        } else {
          lastChar = array[i];
        }
      }
      int ch = array[i] - 'a';
      if (i < len - 1) {
        result += (accu[len - i - 1][ch] - accu[len - i - 2][25]);
      } else {
        result += accu[len - i - 1][ch];
      }
    }
    return result;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println("ab = " + s.getNumberFromChar("ab".toCharArray()));
    System.out.println("ba = " + s.getNumberFromChar("ba".toCharArray()));
    System.out.println("aez = " + s.getNumberFromChar("aez".toCharArray()));
    System.out.println("cde = " + s.getNumberFromChar("cde".toCharArray()));
    System.out.println("hjmoqsu = " + s.getNumberFromChar("hjmoqsu".toCharArray()));
  }
}
